C/sorting.and.searching.cormen.algo/Introduction to Algorithms, Third Edition/code/qui.c

   1 /* quicksort */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 typedef int T;                  /* type of item to be sorted */
   7 typedef int tblIndex;           /* type of subscript */
   8
   9 #define compGT(a,b) (a > b)
  10 #define compLT(a,b) (a < b)
  11
  12 void sortByInsertion(T *x, tblIndex lb, tblIndex ub) {
  13     tblIndex i, j;
  14
  15     for (i = lb + 1; i <= ub; i++) {
  16         T t = x[i];
  17
  18         /* shift down until insertion point found */
  19         for (j = i-1; j >= 0 && compGT(x[j], t); j--)
  20             x[j+1] = x[j];
  21
  22         /* insert */
  23         x[j+1] = t;
  24     }
  25 }
  26
  27 tblIndex partition(T *x, tblIndex lb, tblIndex ub) {
  28
  29     /* select a pivot */
  30     double pivot = x[(lb+ub)/2];
  31
  32     /* work from both ends, swapping to keep   */
  33     /* values less than pivot to the left, and */
  34     /* values greater than pivot to the right  */
  35     tblIndex i = lb - 1;
  36     tblIndex j = ub + 1;
  37     while (1) {
  38         T t;
  39
  40         while (compGT(x[--j], pivot));
  41         while (compLT(x[++i], pivot));
  42         if (i >= j) break;
  43
  44         /* swap x[i], x[t] */
  45         t = x[i];
  46         x[i] = x[j];
  47         x[j] = t;
  48     }
  49
  50     return j;
  51 }
  52
  53 void quickSort(T *x, tblIndex lb, tblIndex ub) {
  54     tblIndex m;
  55
  56     if (lb >= ub) return;
  57     m = partition(x, lb, ub);
  58     quickSort(x, lb, m);
  59     quickSort(x, m + 1, ub);
  60 }
  61
  62 void quickSortImproved(T *x, tblIndex lb, tblIndex ub) {
  63     while (lb < ub) {
  64         tblIndex m;
  65
  66         /* quickly sort short lists */
  67         if (ub - lb <= 50) {
  68             sortByInsertion(x, lb, ub);
  69             return;
  70         }
  71
  72         m = partition(x, lb, ub);
  73
  74         /* eliminate tail recursion and */
  75         /* sort the smallest partition first */
  76         /* to minimize stack requirements    */
  77         if (m - lb <= ub - m) {
  78             quickSortImproved(x, lb, m);
  79             lb = m + 1;
  80         } else {
  81             quickSortImproved(x, m + 1, ub);
  82             ub = m;
  83         }
  84     }
  85 }
  86
  87 void fill(T *a, tblIndex lb, tblIndex ub) {
  88     tblIndex i;
  89     srand(1);
  90     for (i = lb; i <= ub; i++) a[i] = rand();
  91 }
  92
  93 int main(int argc, char *argv[]) {
  94     tblIndex maxnum, lb, ub;
  95     T *a;
  96
  97     /* command-line:
  98      *
  99      *   qui maxnum
 100      *
 101      *   qui 2000
 102      *       sorts 2000 records
 103      *
 104      */
 105
 106     maxnum = atoi(argv[1]);
 107     lb = 0; ub = maxnum - 1;
 108     if ((a = malloc(maxnum * sizeof(T))) == 0) {
 109         fprintf (stderr, "insufficient memory (a)\n");
 110         exit(1);
 111     }
 112
 113     fill(a, lb, ub);
 114     quickSortImproved(a, lb, ub);
 115
 116     return 0;
 117 }